package com.ygu.Enter2;


public class DetectCycle {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        //判断是否存在环
        while (fast!=null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
            //代表有环
            if(fast==slow){
                //有环就继续移动 让slow从起点出发
                ListNode index1 = fast;
                slow = head;
                while (slow!= index1){
                    index1 = index1.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }

    static class ListNode {
        public int val;
        public ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
